'''
https://leetcode.cn/problems/time-needed-to-inform-all-employees/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        graph = [[] for _ in range(n)]
        for v in range(n):
            if v == headID:
                continue
            graph[manager[v]].append(v)

        def dfs(u):
            if not graph[u]:
                return 0
            time = 0
            for v in graph[u]:
                time = max(time, dfs(v))
            return time + informTime[u]
        return dfs(headID)

n, headId = 8, 0
manager = [-1,5,0,6,7,0,0,0]
informTime = [89,0,0,0,0,523,241,519]
print(Solution().numOfMinutes(n, headId, manager, informTime))